package com.zp.self.module.level_4_算法练习.算法.深度优先搜索.递归;

/**
 * @author By ZengPeng
 */
public class 力扣_542_01矩阵 {
    //测试
    public static void main(String[] args) {

//        System.out.println(new 力扣_542_01矩阵().updateMatrix(new int[][]{{0,0,0},{0,1,0},{0,0,0}}));
//        System.out.println(new 力扣_542_01矩阵().updateMatrix(new int[][]{{0,0,0},{0,1,0},{1,1,1}}));
//        System.out.println(new 力扣_542_01矩阵().updateMatrix(new int[][]{{0,1,0,1,1},{1,1,0,0,1},{0,0,0,1,0},{1,0,1,1,1},{1,0,0,0,1}}));
//        System.out.println(new 力扣_542_01矩阵().updateMatrix(new int[][]{{0},{1}}));
        System.out.println(new 力扣_542_01矩阵().updateMatrix(new int[][]{{1,1,0,0,1,0,0,1,1,0},{1,0,0,1,0,1,1,1,1,1},{1,1,1,0,0,1,1,1,1,0},{0,1,1,1,0,1,1,1,1,1},{0,0,1,1,1,1,1,1,1,0},{1,1,1,1,1,1,0,1,1,1},{0,1,1,1,1,1,1,0,0,1},{1,1,1,1,1,0,0,1,1,1},{0,1,0,1,1,0,1,1,1,1},{1,1,1,0,1,0,1,1,1,1}}));
    }

    /**
    题目：给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，
     其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。
     两个相邻元素间的距离为 1 。

     示例 1：
     输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
     输出：[[0,0,0],[0,1,0],[0,0,0]]

     示例 2：
     输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
     输出：[[0,0,0],[0,1,0],[1,2,1]]

    分析：【PR 💗💖💘💝❤】
       1.递归：上下左右的寻找0的位置，距离不断增1 --自己其实用的是动态规划
               优化：记录每个位置离0的距离
            -- 执行用时：6 ms, 在所有 Java 提交中击败了98.77%的用户
       大神.广度优先：先扫描所有0进入队列，在不断弹出队列，坐标查找周围的1，距离+1，再将周围的1加入到队列末尾

    边界值 & 注意点：
       1.递归出现了你问我，我问你的情况!!   解： 先问上左，再问下右
       2.比下右时 ，防止初始位置下右都还不确定。 解：所以应该从 下开始刷新
     **/
    public int[][] updateMatrix(int[][] mat) {
        int[][] res =new int[mat.length][mat[0].length];
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++)
                res[i][j]=-1;
        }
        for (int i = 0; i < mat.length; i++) {
            for (int j = 0; j < mat[0].length; j++)
                res[i][j] = dfs(mat,i,j,res);
        }
        //比下右： 防止 初始位置下右都还不确定，所以应该从 下开始刷新
        int indexX = res.length-1,indexC=res[0].length-1;
        for (int i = res.length-1; i >=0 ; i--) {
            for (int j = res[0].length-1; j >=0; j--) {
                if (j != indexC)
                    res[i][j] = Math.min(res[i][j], res[i][j+ 1]+1);
                if (i != indexX)
                    res[i][j] = Math.min(res[i][j], res[i + 1][j]+1);
            }
        }
        return res;
    }

    private int dfs(int[][] mat, int x, int y, int[][] res) {
        if(res[x][y]!=-1) //这里不等于-1 ，属于优化，可更快知道这个值是否填充过，不用二次比较：mat[x][y]==0; 快了一毫秒【细节】
            return res[x][y];
        if(mat[x][y]==0)
            return 0;
        int minDistance=10001;
        if(x>0)
            minDistance = Math.min(minDistance,dfs(mat,x-1,y,res));
        if(y>0)
            minDistance = Math.min(minDistance,dfs(mat,x,y-1,res));
        res[x][y] = minDistance+1;
        return  res[x][y];
    }
}
